package linkedList;

/** 单链表 */
public class SingleLinkedListDemo {
  public static void main(String[] args) {
    SingleLinkedList linkedList = new SingleLinkedList();
    Node2 node1 = new Node2(1, "WWS", 1);
    Node2 node2 = new Node2(2, "IRJ", 2);
    Node2 node3 = new Node2(3, "BFG", 3);
    Node2 node4 = new Node2(4, "VCX", 4);
    /*linkedList.add(node1);
    linkedList.add(node2);
    linkedList.add(node3);
    linkedList.add(node4);*/

    linkedList.addByOrder(node4);
    linkedList.addByOrder(node1);
    linkedList.addByOrder(node2);
    linkedList.addByOrder(node3);

    linkedList.list();

    System.out.println("修改后");
    linkedList.update(new Node2(6,"vrg",30));
    linkedList.list();

    System.out.println("删除后");
    linkedList.delete(1);
    linkedList.list();

    int length = linkedList.getLength();
    System.out.println("有效结点个数为："+length);

    Node2 lastNode = linkedList.getLastNode(4);
    System.out.println("倒数第k个结点为"+lastNode);

    linkedList.reverse();
    System.out.println("反转后的链表：");
    linkedList.list();
  }




}



class Node {

  public int id;
  public String name;
  public int age;
  public Node2 next;

  public Node(int id, String name, int age) {
    this.id = id;
    this.name = name;
    this.age = age;
  }

  public Node() {}

  @Override
  public String toString() {
    return "Node2{" + "id=" + id + ", name='" + name + '\'' + ", age=" + age + '}';
  }
}

class SingleLinkedList {

  private final Node2 head = new Node2();

  public Node2 getHead(){
    return this.head;
  }

  Node2 temp = head;
  // 插入链表
  public void add(Node2 node) {
    while (true) {
      if (temp.next == null) {
        break;
      }
      temp = temp.next;
    }
    temp.next = node;
  }

  //按顺序插入链表
  public void addByOrder(Node2 node){

    Node2 temp=head;
    boolean flag = false;
    while (temp.next!=null&&node.id>=temp.next.id){
      if (node.id == temp.next.id){
        flag=true;
        break;
      }
      temp = temp.next;
    }
    if (flag){
      System.out.println("id重复");
    }else{
      node.next=temp.next;
      temp.next=node;
    }
  }

  //修改链表
  public void update(Node2 node){

    if (head.next==null){
      System.out.println("链表为空");
      return;
    }
    Node2 temp = head.next;
    boolean flag = false;
    while (temp.next!=null){
      temp=temp.next;
      if (temp.id==node.id){
        flag = true;
        break;
      }
    }
    if (flag){
      temp.name=node.name;
      temp.age=node.age;
    }else {
      System.out.println("未找到节点id为"+node.id+"的结点");
    }
  }

  //删除结点
  public void delete(int id){
    if (head.next==null){
      System.out.println("链表为空");
      return;
    }
    Node2 temp = head;
    boolean flag = false;
    while (true){
      if (temp.next==null){
        break;
      }
      if (temp.next.id==id){
        flag = true;
        break;
      }
      temp=temp.next;
    }
    if (flag){
      temp.next=temp.next.next;
    }else {
      System.out.println("未找到id为"+id+"的结点");
    }

  }

  // 遍历链表
  public void list() {
    if (head.next == null) {
      System.out.println("链表为空");
      return;
    }
    Node2 temp = head;
    while (true) {
      temp=temp.next;
      System.out.println(temp);
      if (temp.next==null){
        return;
      }
    }
  }

  //获取链表有效节点个数
  public  int getLength() {
    if (head.next==null){
      return 0;
    }
    Node2 cur=head;
    int length=0;
    while (cur.next!=null){
      length++;
      cur=cur.next;
    }
    return length;
  }

  //得到链表的倒数第k个结点
  public Node2 getLastNode(int k){
    if (head.next==null){
      return null;
    }
    int length = getLength();
    if (k<=0||k>length){
      return null;
    }
    Node2 cur=head.next;
    for (int i = 0; i < length - k; i++) {
      cur=cur.next;
    }
    return cur;
  }

  //反转链表
  public void reverse(){

    if (head.next==null||head.next.next.next==null){
      return;
    }
    Node2 reverseHead=new Node2();
    Node2 cur=head.next;
    Node2 next=null;
    while(cur!=null){
      next=cur.next;
      cur.next=reverseHead.next;
      reverseHead.next=cur;
      cur=next;
    }
    head.next=reverseHead.next;
  }
}
